<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Permutation in String</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="permutation-in-string">Permutation in String</h1>
<h1 id="1-lc-567-permutation-in-string">1. LC 567. Permutation in String</h1>
<ul>
<li><a href="https://leetcode.com/problems/permutation-in-string/">https://leetcode.com/problems/permutation-in-string/</a></li>
</ul>
<p>Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.</p>
<pre><code><code><div>Example 1:

Input: s1 = &quot;ab&quot; s2 = &quot;eidbaooo&quot;
Output: True
Explanation: s2 contains one permutation of s1 (&quot;ba&quot;).

Example 2:

Input:s1= &quot;ab&quot; s2 = &quot;eidboaoo&quot;
Output: False
 

Constraints:

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].
</div></code></code></pre>
<p>使用2个Counter</p>
<ul>
<li>第一个Counter记录&quot;有效字符&quot;和频率</li>
<li>第二个Counter记录遍历过程中的&quot;有效字符&quot;和频率</li>
</ul>
<p>用滑动窗口，保持滑动窗口大小一直是m, 如果两个Counter相等，就是有效的Permutation</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> Counter

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">checkInclusion</span><span class="hljs-params">(self, s1: str, s2: str)</span> -&gt; bool:</span>
        p1 = Counter(s1)
        p2 = Counter()
        m = len(s1)
        n = len(s2)
        
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            cr = s2[i]
            <span class="hljs-keyword">if</span> cr <span class="hljs-keyword">in</span> p1:
                p2[cr] += <span class="hljs-number">1</span>
                
            <span class="hljs-keyword">if</span> i &gt;= m:
                cr2 = s2[i-m]
                <span class="hljs-keyword">if</span> cr2 <span class="hljs-keyword">in</span> p1:
                    p2[cr2] -= <span class="hljs-number">1</span>
                    
            <span class="hljs-keyword">if</span> p1 == p2:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
</div></code></pre>
<h1 id="2-lc-438-find-all-anagrams-in-a-string">2. LC 438. Find All Anagrams in a String</h1>
<ul>
<li><a href="https://leetcode.com/problems/find-all-anagrams-in-a-string/">https://leetcode.com/problems/find-all-anagrams-in-a-string/</a></li>
</ul>
<p>Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.</p>
<p>Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.</p>
<p>The order of output does not matter.</p>
<pre><code><code><div>Example 1:

Input:
s: &quot;cbaebabacd&quot; p: &quot;abc&quot;

Output:
[0, 6]

Explanation:
The substring with start index = 0 is &quot;cba&quot;, which is an anagram of &quot;abc&quot;.
The substring with start index = 6 is &quot;bac&quot;, which is an anagram of &quot;abc&quot;.
Example 2:

Input:
s: &quot;abab&quot; p: &quot;ab&quot;

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is &quot;ab&quot;, which is an anagram of &quot;ab&quot;.
The substring with start index = 1 is &quot;ba&quot;, which is an anagram of &quot;ab&quot;.
The substring with start index = 2 is &quot;ab&quot;, which is an anagram of &quot;ab&quot;.
</div></code></code></pre>
<p>我的解法</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> Counter, defaultdict

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findAnagrams</span><span class="hljs-params">(self, s: str, p: str)</span> -&gt; List[int]:</span>
        c = Counter(p)
        m = defaultdict(int)
        start = <span class="hljs-number">0</span>
        end = <span class="hljs-number">0</span>
        n = len(s)
        ans = []
        <span class="hljs-keyword">while</span> end &lt; n:
            cr = s[end]
            <span class="hljs-keyword">if</span> cr <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> c:
                end += <span class="hljs-number">1</span>
                start = end
                m = defaultdict(int)
                <span class="hljs-keyword">continue</span>
                
            m[cr] += <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> m[cr] &gt; c[cr]:
                <span class="hljs-keyword">while</span> start &lt;= end:
                    cr2 = s[start]
                    start += <span class="hljs-number">1</span>
                    m[cr2] -= <span class="hljs-number">1</span>
                    <span class="hljs-keyword">if</span> m[cr] &lt;= c[cr]:
                        <span class="hljs-keyword">break</span>
                    
            
            flag = <span class="hljs-literal">True</span>
            <span class="hljs-keyword">for</span> key <span class="hljs-keyword">in</span> c.keys():
                <span class="hljs-keyword">if</span> m[key] != c[key]:
                    flag = <span class="hljs-literal">False</span>
                    <span class="hljs-keyword">break</span>
            <span class="hljs-keyword">if</span> flag:
                ans.append(start)
            
            <span class="hljs-comment">#print(f"start={start} end={end} m={m}")</span>
            end += <span class="hljs-number">1</span>
                
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<p>官方解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findAnagrams</span><span class="hljs-params">(self, s: str, p: str)</span> -&gt; List[int]:</span>
        ns, np = len(s), len(p)
        <span class="hljs-keyword">if</span> ns &lt; np:
            <span class="hljs-keyword">return</span> []

        p_count, s_count = [<span class="hljs-number">0</span>] * <span class="hljs-number">26</span>, [<span class="hljs-number">0</span>] * <span class="hljs-number">26</span>
        <span class="hljs-comment"># build reference array using string p</span>
        <span class="hljs-keyword">for</span> ch <span class="hljs-keyword">in</span> p:
            p_count[ord(ch) - ord(<span class="hljs-string">'a'</span>)] += <span class="hljs-number">1</span>
        
        output = []
        <span class="hljs-comment"># sliding window on the string s</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(ns):
            <span class="hljs-comment"># add one more letter </span>
            <span class="hljs-comment"># on the right side of the window</span>
            s_count[ord(s[i]) - ord(<span class="hljs-string">'a'</span>)] += <span class="hljs-number">1</span>
            <span class="hljs-comment"># remove one letter </span>
            <span class="hljs-comment"># from the left side of the window</span>
            <span class="hljs-keyword">if</span> i &gt;= np:
                s_count[ord(s[i - np]) - ord(<span class="hljs-string">'a'</span>)] -= <span class="hljs-number">1</span>
            <span class="hljs-comment"># compare array in the sliding window</span>
            <span class="hljs-comment"># with the reference array</span>
            <span class="hljs-keyword">if</span> p_count == s_count:
                output.append(i - np + <span class="hljs-number">1</span>)
        
        <span class="hljs-keyword">return</span> output
</div></code></pre>

    </body>
    </html>